//
//  459. 重复的子字符串.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/7/12.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
class Solution459 {
    func repeatedSubstringPattern(_ s: String) -> Bool {
        let sArray = Array(s)
        let next = getNext(sArray)
        let length = s.count
        // 手动计算出next表。就能发现规律。
        if next[length - 1] != 0 && length % (length - (next[length - 1] )) == 0 {
            return true
        }
        return false
    }
    func getNext(_ s: [Character]) -> [Int] {
        var next: [Int] = Array(repeating: 0, count: s.count)
        
        var j = 0
        var i = 1
        next[0] = j
        while i < s.count {
            // 不相等时, j要进行回退
            while j > 0 && s[j] != s[i] {
                j = next[j - 1]
            }
            // 相等一起向后走
            if s[j] == s[i] {
                j += 1
            }
            next[i] = j
            i += 1
        }
        return next
    }
    static func test() {
        let s = "abcabcabcabc"
        let solution = Solution459()
        let result = solution.repeatedSubstringPattern(s)
        print(result)
    }
}
